# 把指定的所有货放到不同的船上，使得所有船的租金和最少
#
# 转换一下目标，使每个船的单位重量租金最少（单船的吨租金=单船的租金/单船装的货物重量总和）
# 吨租金的性价比最高
import pandas as pd
import numpy as np
data = {'huowu_name':[],
        'huowu_code':[],
        'huowu_wt':[],
        'tag':[]}
data_huowu=pd.DataFrame(data)
data_huowu.sort_values(by="huowu_wt", inplace=True, ascending=True)
data_huowu = data_huowu.reset_index(drop=True)
huowu_list = data_huowu['huowu_code'].to_list()
data = {'ship_wt':[],
        'ship_price':[]}
data_ship=pd.DataFrame(data)
data_ship.sort_values(by="ship_wt", inplace=True, ascending=True)
data_ship = data_ship.reset_index(drop=True)
def cal_oneship_best(ship_wt_tmp,data_huowu,huowu_code_tmp):

    # 应该是一个01背包问题
    data_huowu_0 = data_huowu[(data_huowu['tag'] == 0) & (data_huowu['huowu_code'] != huowu_code_tmp)]
    data_huowu_0.sort_values(by="huowu_wt", inplace=True, ascending=True)
    data_huowu_0 = data_huowu_0.reset_index(drop=True)
    huowu_list_0 = data_huowu_0['huowu_wt'].to_list()
    huowu_code_list_0 = data_huowu_0['huowu_code'].to_list()
    huowu_list = [huowu_code_tmp]
    w = huowu_list_0
    p = w
    #为了尽可能的装，所以价值就是重量
    n = len(p)
    v = int(ship_wt_tmp)
    lists = []
    arr = [[0] * (v+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,v+1):
            if w[i-1] <= j:
                arr[i][j] = max(arr[i-1][j],p[i-1]+ arr[i-1][j-w[i-1]])
            else:
                arr[i][j] = arr[i-1][j]
    remain = v
    for i in range(n, 0, -1):
        if arr[i][remain] > arr[i-1][remain]:
            lists.append(i)
            huowu_list.append(huowu_code_list_0[i-1])
            #i当前物品的在list中的编号
            remain -= w[i-1]
    print(arr[-1][-1])
    #最优的分配（尽可能的装）
    for i in range(len(lists)):
        print(lists[len(lists)-i-1],end='')
    huowu_total_wt = arr[-1][-1]
    return huowu_list,huowu_total_wt



df_out = pd.DataFrame(columns=['ship_index', 'ship_wt', 'huowu_list', 'ship_price', 'huowu_total_wt'])
dict = {}
ship_num = 1
for huowu_tmp in huowu_list:
    data_huowu_tmp = data_huowu[(data_huowu['huowu_code'] == huowu_tmp)]
    data_huowu_tmp = data_huowu_tmp.reset_index(drop=True)
    tag_tmp = data_huowu_tmp.loc[0]['tag']
    huowu_wt_tmp = data_huowu_tmp.loc[0]['huowu_wt']
    huowu_code_tmp = data_huowu_tmp.loc[0]['huowu_code']
    if tag_tmp == 1:
        continue
    else:
        #run单船吨租金最少的函数
        df_xingjiabi = pd.DataFrame(columns=['ship_wt', 'huowu_list', 'ship_price', 'huowu_total_wt', 'xingjiabi'])
        dict_xingjiabi = {}
        for index, row in data_ship.iterrows():
            ship_wt_tmp = row['ship_wt']
            ship_price_tmp = row['ship_price']
            if huowu_wt_tmp>ship_wt_tmp:
                continue
            huowu_list, huowu_total_wt = cal_oneship_best(ship_wt_tmp-huowu_wt_tmp,data_huowu,huowu_code_tmp)
            xingjiabi_tmp = ship_price_tmp / huowu_total_wt
            dict_xingjiabi['huowu_list'] = huowu_list
            dict_xingjiabi['huowu_total_wt'] = huowu_total_wt +huowu_wt_tmp
            dict_xingjiabi['ship_price'] = ship_price_tmp
            dict_xingjiabi['ship_wt'] = ship_wt_tmp
            dict_xingjiabi['xingjiabi'] = xingjiabi_tmp
            new_row = pd.Series(dict_xingjiabi)
            df_xingjiabi = df_xingjiabi.append(new_row, ignore_index=True)
        print(df_xingjiabi)
        df_xingjiabi.sort_values(by="xingjiabi", inplace=True, ascending=True)
        df_xingjiabi = df_xingjiabi.reset_index(drop=True)
        huowu_list_out = df_xingjiabi.loc[0]['huowu_list']
        huowu_total_wt_out = df_xingjiabi.loc[0]['huowu_total_wt']
        ship_price_out = df_xingjiabi.loc[0]['ship_price']
        ship_wt_out = df_xingjiabi.loc[0]['ship_wt']
        dict['huowu_list'] = huowu_list_out
        dict['huowu_total_wt'] = huowu_total_wt_out
        dict['ship_price'] = ship_price_out
        dict['ship_wt'] = ship_wt_out
        dict['ship_index'] = ship_num
        new_row = pd.Series(dict)
        df_out = df_out.append(new_row, ignore_index=True)
        ship_num = ship_num + 1
        def __cal_new_tag(x):
            if x.tag==1 or x.huowu_code in huowu_list_out:
                rst = 1
            else:
                rst =0
            return rst
        data_huowu['new_tag'] = data_huowu.apply(lambda x: __cal_new_tag(x), axis=1)
        data_huowu.drop(['tag'], axis=1, inplace=True)
        data_huowu.rename(columns={'new_tag': 'tag'}, inplace=True)










